package io.tec.cloud.algorithm.c01_v20220601;

import java.util.Arrays;

/**
 * 在一个有序数组中，找大于等于某个数最左侧的位置
 */
public class BSNearLeft {

    public static int nearestLeftIndex(int[] arr, int target) {
        int targetIndex = -1;
        int L = 0;
        int R = arr.length - 1;
        int mid;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] >= target) {
                targetIndex = mid;
                R = mid - 1;
            } else if (arr[mid] < target) {
                L = mid + 1;
            }
        }
        return targetIndex;
    }

    public static int test(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= target) {
                return i;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        int testTimes = 1000000;
        int maxValue = 500;
        int maxLength = 50;

        for (int t = 0; t < testTimes; t++) {
            int[] original = SortTestUtil.generatorRandomArray(maxValue, maxLength);
            Arrays.sort(original);
            int[] arr1 = SortTestUtil.copyArray(original);
            int[] arr2 = SortTestUtil.copyArray(original);
            int target = (int) ((Math.random() * maxValue) + 1);
            int i1 = nearestLeftIndex(arr1, target);
            int i2 = test(arr2, target);
//            SortTestUtil.p(original);
//            System.out.println("target = " + target);
//            System.out.println(i1 + " " + i2);
            if (i1 != i2) {
                System.out.println(target);
                System.out.println("error");
                return;
            }
        }
        System.out.println("finish");
    }
}
